Most cryptosystems require secure key management. For example, in public-key based security systems, private keys must be protected so that attackers cannot use the keys to forge digital signatures, modify data, or decrypt sensitive information. Systems employing symmetric cryptography similarly require that keys be kept secret. Therefore, well-designed cryptographic algorithms and protocols should prevent attackers, who eavesdrop on communications, from breaking into secure systems.
Further, Cryptographic algorithms and protocols traditionally require tamper-resistant hardware or other implementation-specific measures to prevent attackers from accessing or finding the secret keys.
If the cryptosystem designer can safely assume that the key management system is completely tamper-proof and will not reveal any information relating to the keys except via the messages and operations defined in the protocol, then previously known cryptographic techniques are often sufficient for good security. However, it is currently extremely difficult to make hardware key management systems that provide good security, particularly in low-cost unshielded cryptographic devices for use in applications where attackers will have physical control over the device. For example, cryptographic tokens (such as smartcards used in electronic cash and copy protection schemes) must protect their keys even in potentially hostile environments. A token is a device that contains or manipulates cryptographic keys that need to be protected from attackers. Forms in which tokens may be manufactured include, without limitation, smartcards, specialized encryption and key management devices, secure telephones, secure picture phones, secure web servers, consumer electronics devices using cryptography, secure microprocessors, and other tamper-resistant cryptographic systems.
If timing is the only source of leaked information, securing the device is often relatively straightforward. For example, previously known countermeasures against attacks involving information leaking from cryptosystems employ large and often expensive physical shielding and/or careful filtering of inputs and outputs (e.g., U.S. government Tempest specifications). Unfortunately, these techniques are difficult to apply in constrained engineering environments. For example, physical constraints (such as size and weight), cost, and the need to conserve power can often prevent the use of such techniques. It is also known to use certain computational techniques to equalize timing and hence, protect the system from timing attacks. However, sources of information leakage other than timing (e.g., a device's power consumption) provide other avenues of attacks that are collectively called Differential Power Attacks (DPA). It would therefore be advantageous to protect the devices' internal operations themselves instead of, or in addition to, simply externally masking the devices' timing or other fluctuations.
Some techniques for hindering external monitoring of cryptographic secrets are known, such as using power supplies with large capacitors to mask fluctuations in power consumption, enclosing devices in well-shielded cases to prevent electromagnetic radiation, message blinding to prevent timing attacks, and buffering of inputs/outputs to prevent signals from leaking out on I/O lines. Shielding, introduction of noise, and other such countermeasures are often, however, of limited value, since skilled attackers can still find keys by amplifying signals and filtering out noise or by averaging data collected from many operations. Furthermore, in smartcards and other tamper-resistant chips, these countermeasures are often inapplicable or insufficient due to reliance on external power sources, impracticality of shielding, and other physical constraints. The use of blinding and constant-time mathematical algorithms to prevent timing attacks is also known, but does not prevent more complex attacks such as power consumption analysis particularly if the system designer cannot perfectly predict what information will be available to an attacker, as is often the case before a device has been physically manufactured and characterized.
Other than the physical countermeasures already outlined, there are some countermeasures that are not physical in nature, but, alternatively, protect cryptographic algorithms from DPA by applying slight modifications to the algorithms themselves. Hence, the cost involved in applying the physical measures will vanish. However, such methods introduce their own cost that results from the additional operations performed in order to de-correlate the power-consumption of the circuit with the values of the hidden information that are processed.
Among these are the method disclosed by Kocher et al in the U.S. Pat. No. 6,298,442, by which the key is protected during the operation of modular exponentiation. Through the fact that the operations of modular squaring and modular multiplications can be performed on the same hardware, they proceed by recoding the key into a series of separate multiplication and squaring steps. Hence, the power consumption of the circuit and the memory access will be independent of the original key digits. This method is clearly limited to field exponentiation which can be implemented as a sequence of field squaring and multiplication. Squaring can be considered as a special case of multiplication. The application of this method to elliptic curve cryptography is not practical since the basic operations of scalar multiplication of point doubling and point addition are completely different from each other. They are implemented using different mathematical expressions.
Another technique is the one disclosed by Kocher et al in the U.S. Pat. Nos. 6,304,658 and 6,381,699, and the US patent applications Nos. 20010002486 and 20030028771. In these publications, the authors introduce the concept of a “self-healing” system, which is the system in which the leaked information loses its value by time (i.e., after the encryption of several messages). They achieve such a property by dynamically changing the key, which renders all the leaked information about the old key useless. However, this introduces some computational overhead. Another technique, introduced by the same authors, is disclosed in a US patent application No. 20020124178. As disclosed therein the authors suggest that a piece of hardware can skip some clock cycles to confuse an observer. This, however, introduces some hardware and time inefficiency and causes problems, as stated in the publication itself, when performing serial communication, which requires strict timing.
Another publication, the US Patent Application No. 20010048741 by Okeya, uses a different strategy to protect the cryptographic process. In this method, which is specific to elliptic curve cryptography, addition and doubling are performed in every step, which creates a pre-determined order of execution that is independent of the key value. Likewise, Handschuh, in the US Patent Application No. 20010048742, introduces a method in which the key is represented as the difference of two quantities. Then, each of these quantities is used in a scalar multiplication, of which the results are subtracted to get the needed result. Moreover, the US Patent Application No. 20030044014, authored by Liardet, discloses random multiples of the modulus to randomize the performed modular operations.
One successful measure against DPA on elliptic curve cryptosystems is based on using randomized projective coordinates. This is a measure against the attack method of observing whether a specific value appears or not in elliptic curve scalar multiplication calculation, and inferring a scalar value from the observed result.
It is significant to note that the underlying basis of randomized projective coordinate is that by multiplication with a random value, the appearance of such specific values is uncorrelated with the value of the scalar multiplicand.
It should be pointed out that the application of randomized projective coordinates is rather restricted because of its major drawback of requiring expensive field multiplication operations. For this reason, it is usually applied once per elliptic curve scalar multiplication.
There are some common characteristics among all the discussed countermeasures. Firstly, all of them introduce a significant amount of inefficiency. To prevent the attack by power analysis, an extra amount of calculation other than necessary has to be carried out using secret information so that the dependence of the cryptographic processing on the secret information is weakened. Thus, time required for the cryptographic processing increases and the cryptographic processing efficiency will be lowered noticeably in a computer, such as a smart card, which is slow in calculation speed, or a server managing an enormous number of cryptographic processes.
Clearly, as side-channel attacks become more sophisticated, more involved countermeasures need to be applied. This ultimately leads to the requirements of more elaborate and computationally efficient countermeasures.
Another common characteristic of the countermeasure discussed above is that all of them help only in enhancing the immunity of the cryptographic system against DPAs. They do not provide any provisions to enhance the security of the underlying cryptographic protocol against cryptanalysis.
It would be very significant to have a framework/methodology where the introduced countermeasures are not only effective against side channel attacks but also increase the security of the underlying cryptographic protocol.
This is important since it can be argued that a framework/methodology that enhances the security of the underlying protocol implies that a smaller key size would be needed than that required by an equivalent protocol with no enhanced security measures. It can then be argued that the enhanced security of the underlying cryptographic protocol would also compensate for any inefficiency introduced by the added countermeasure since it would allow the use of a smaller key size.
Clearly, such a comprehensive framework for enhancing the security of cryptographic applications is highly desirable.
Two further approaches to methods for communicating securely over an insecure communication channel are disclosed in the co-pending applications of Mohammad K. Ibrahim entitled “Elliptic Polynomial Cryptography with Multi X-Coordinates Embedding” Ser. No. 10/911,701 filed Aug. 5, 2004 and “Elliptic Polynomial Cryptography with Multi Y-Coordinates Embedding” Ser. No. 10/911,702 filed Aug. 5, 2004 both of which are assigned to the same Assignee as the present invention and both of which are incorporated herein in their entirety by reference.